'''
希尔排序是插入排序的一种更高效的改进版本，也称为缩小增量排序。它通过将原来整个待排序的记录序列分割成为若干个子序列分别进行直接插入排序，
待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。这种方法的基本思想是将待排序的元素按下标的一定增量分组，
对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的元素越来越多，当增量减至1时，整个文件恰被分成一组，算法终止。
算法步骤：
选择一个增量序列：通常，初始增量取数组长度的一半，之后每次减半，直到增量为1。
分组：根据当前增量，将数组元素分组，所有距离为增量的元素在同一组。
组内排序：对每组使用插入排序算法进行排序。
减小增量：重复上述分组和排序过程，直到增量为1。
时间复杂度分析
希尔排序的时间复杂度依赖于增量序列的选择。对于最坏情况，使用最初提出的希尔增量（每次减半），时间复杂度为O(n2)。然而，
通过一些优化的增量序列（如Hibbard增量序列、Sedgewick增量序列等），可以显著改进性能。最好的已知希尔排序时间复杂度为O(n(3/2))，
但这取决于增量的选择。
在平均情况下，希尔排序的性能也优于基本的插入排序，特别是对于较大的数据集，其效率提升更加明显。
空间复杂度分析
希尔排序是一种就地排序算法（in-place sorting algorithm），它只需要一个额外的空间来存储临时变量（在插入排序的过程中可能需要），
因此其空间复杂度为O(1)。这意味着希尔排序不需要额外的存储空间来存储排序过程中的数据，它直接在原数组上进行排序。
总结
希尔排序不是稳定排序通过引入增量序列，使得插入排序的效率在数据规模较大时依然保持较高的效率。虽然其最坏情况下的时间复杂度与基本插入排序相同，
但通过选择合适的增量序列，可以显著提高排序的平均性能。希尔排序是一种不稳定的排序算法，因为它可能会改变相等元素的相对顺序。
然而，由于其简单的实现和较好的平均性能，希尔排序在许多实际应用中仍然被广泛使用。
'''
import random
class Solution:
    def shellSort(self,arr):
        n = len(arr)
        #初始增量
        gap = n//2
        while gap>0:
            #对每个分组进行插入排序
            for i in range(gap,n):
                temp = arr[i]
                j = i
                #插入排序
                while j>=gap and arr[j-gap]>temp:
                    arr[j] = arr[j-gap]
                    j -= gap
                arr[j] = temp
            #缩减增量
            gap //= 2
        return arr
#示例
if __name__ == '__main__':
    arr = random.sample(range(1,1000),10)
    print(arr)
    print(Solution().shellSort(arr))